#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    unordered_map<int, int> hash;
    int maxCount = 0, maxVal = 0;
    for (auto e : barcodes)
    {
        if (maxCount < ++hash[e])
        {
            maxCount = hash[e];
            maxVal = e;
        }
    }

    int n = barcodes.size();
    vector<int> ret(n);
    int index = 0;
    for (int i = 0; i < maxCount; ++i)
    {
        ret[index] = maxVal;
        index += 2;
    }

    hash.erase(maxVal);
    for (auto [x, y] : hash)
    {
        for (int i = 0; i < y; ++i)
        {
            if (index >= n)
                index = 1;
            ret[index] = x;
            index += 2;
        }
    }

    return ret;
}

int main()
{
    vector<int> arr = { 1,1,1,2,2,2 };
    rearrangeBarcodes(arr);
	return 0;
}